#include <stdlib.h>
#include <stdio.h>
#define ElementType int
typedef struct 
{
   	ElementType data;
	struct node *LChild,*RChild;
	int LTag,RTag;
}ThreadBinTreeNode,*TreeNode;


//线索二叉树
void InThreadHelp(ThreadBinTreeNode *cur, ThreadBinTreeNode *pre) 
{
	if (cur != NULL)
	{	
		if (cur->LTag == 0)		
			InThreadHelp(cur->LChild, pre);		
		if(cur->LChild == NULL)
		{	
			cur->LChild = pre;			
			cur->LTag =1;			
	}
		else

		{	
			cur->LTag = 0;		
		}
		if(pre != NULL && pre->RChild == NULL)
		{	
			pre->RChild = cur; 						pre->RTag = 1;	
  		}
  		else if (pre != NULL)
		{	
			pre->RTag = 0;		
		}
		pre = cur;					
		
		if (cur->RTag == 0)		
			InThreadHelp(cur->RChild, pre);
	}
}
//查找后继结点
ThreadBinTreeNode  *inorderNext(ThreadBinTreeNode  *pointer)
{
	TreeNode q;
	if (pointer->RTag==1) return(pointer->RChild);
 else {q=pointer->RChild; /* 找右子树最先访问的结点 */
       while (q->LTag==0) q=q->LChild;
        return(q);
     }
}
ThreadBinTreeNode *CreateBiTree(){
    ThreadBinTreeNode *T;
    int ch;
    scanf("%d",&ch);
    if(ch==0) T=NULL;
    else{
        T=(ThreadBinTreeNode *)malloc(sizeof(ThreadBinTreeNode));
        T->data=ch;
        T->LChild=CreateBiTree();
        T->RChild=CreateBiTree();
		
    }
    return T;
}
void PrintTree(ThreadBinTreeNode* T){
    if(T!=NULL){
        if(T->LChild!=NULL&&T->RChild!=NULL)
        printf("%d",T->data);
        PrintTree(T->LChild);
        PrintTree(T->RChild);
    }
   
}
int main(){
	ThreadBinTreeNode *T,*P=NULL;
   	T=CreateBiTree();
	InThreadHelp(T,P);

	PrintTree(T);
}